import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[] f=new int[triangle.size()];
        f[0]=triangle.get(0).get(0);
        for (int i=1;i<triangle.size();i++){
            f[i]=f[i-1]+triangle.get(i).get(i);
            for (int j=i-1;j>=1;j--){
                f[j]=Math.min(f[j],f[j-1])+triangle.get(i).get(j);
            }
            f[0]=f[0]+triangle.get(i).get(0);
        }
        return Arrays.stream(f).min().getAsInt();
    }

    public static void main(String[] args) {
        List<List<Integer>> lists=new ArrayList<>();
        lists.add(Arrays.asList(2));
        lists.add(Arrays.asList(3,4));
        lists.add(Arrays.asList(6,5,7));
        lists.add(Arrays.asList(4,1,8,3));
        System.out.println(new Solution120().minimumTotal(lists));
    }
}
